Some multi-processor data processing systems include a number of data processors coupled to a number of memory modules through an interconnection network. The interconnection network may employ an Omega-type switch which includes log(n) stages of n/2 two-by-two switches, where n represents the number of ports being serviced by the switch. One type of switch is known as a combining switch which is used to combine multiple messages which are addressed to the same memory location in order to reduce the number of accesses to that memory location. By combining messages the effects of "hot spot" loading are reduced and the bandwidth of the interconnection network is increased. A decombining switch is subsequently employed to "decombine" responses from memory modules and transmit the responses back to the processors.
FIG. 1 illustrates a conventional 2.times.2 combining switch 1 comprised of two substantially identical halves. For convenience only one half of the switch will be discussed, the corresponding structure in the other switch half being designated by a primed reference number. Each switch half includes two FIFO register files, one being known as a Chute FIFO 2 and the other being known as a Queue FIFO 3. The Chute and Queue FIFOs each have an equal number of storage locations and are employed to store messages before transmission to the network of memory modules (not shown). Typically, if there are no contentions or congestions at the switch output port 4 and the Queue 3 is empty, incoming processor messages from input ports I and J are routed directly to the output port 4 via a multiplexer 5. If the Queue 3 is not empty the incoming message is temporarily stored in an input register 6 and compared by a comparator 7 to all existing messages in the Queue to determine if the incoming message is directed to a memory location already associated with a queued message. If a match is not found the incoming registered message is stored in the next available location within the Queue FIFO 3. If a match is detected by the comparator 7 the incoming message is stored instead in the Chute FIFO 2 at a location corresponding to the storage location of the matched message in the Queue 3. Subsequently both the Chute and Queue messages are directed to an arithmetic logic unit (ALU) 8, via ALU input registers 9a and 9b, to combine and generate a single message. Information required for decombining the message on its return from the memory module is sent to a Wait Buffer in an associated decombining switch (not shown).
One significant disadvantage of such conventional combining switches is that the Chute FIFO register file occupies a significant portion of available integrated circuit area. For example, it can be shown that the Chute FIFO 2 can occupy thirty six percent of the data path area as compared to approximately forty five percent for the Queue and ten percent for the ALU. This significant area requirement, and the associated power requirement, for the Chute is especially disadvantageous if the majority of messages sent through the network are not combinable, resulting in only infrequent use of the Chute FIFO.
Another significant disadvantage of such conventional combining switches is that all output from the Queue, whether or not there is a corresponding entry in the Chute, is directed through the ALU. Thus, some finite amount of time is required for the message to pass through the ALU even for those messages which are not combined.
Typically an interconnection network is comprised of a plurality of 2.times.2 combining switches, such as an 8.times.8 network. It can therefore be appreciated that an improved packing density, higher speed and reduced power consumption of each of the 2.times.2 switches would result in an overall improvement in network performance.
It is therefore one object of the invention to provide a combining switch which operates at a higher speed than conventional combining switches.
It is another object of the invention to provide a combining switch which, for each switch half, includes only a Queue FIFO register and which directs messages directly from the Queue FIFO to the switch output port.
It is still another object of the invention to provide a combining switch which has a significant reduction in required integrated circuit surface area, which requires less operating power, and which operates at a higher speed than conventional combining switches.